// 求最长增长子序列长度
export function lis(nums: number[]): number[] {
  const len = nums.length
  const dp = []
  dp[0] = 1
  for (let i = 1; i < len; i++) {
    dp[i] = 1
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[j] + 1, dp[i])
      }
    }
  }
  return dp
}
export function lengthOfLIS(nums: number[]): number {
  return Math.max(...lis(nums))
}
// 求最长增长子序列
export function arrayOfLIS(nums: number[]): number[] {
  const dp = lis(nums)
  const result = [nums[0]]
  let temp = 0
  for (let i = 1; i < dp.length; i++) {
    if (dp[i] > dp[temp]) {
      result.push(nums[i])
      temp = i
    } else if (dp[i] === dp[temp]) {
      if (nums[i] < nums[temp]) {
        result[result.length - 1] = nums[i]
        temp = i
      }
    }
  }
  return result
}
